#include <bits/stdc++.h>
using namespace std;

/*
2444. 统计定界子数组的数目
已解答
困难
相关标签
相关企业
提示
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

子数组中的 最小值 等于 minK 。
子数组中的 最大值 等于 maxK 。
返回定界子数组的数目。

子数组是数组中的一个连续部分。

 

示例 1：

输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
示例 2：

输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。
 

提示：

2 <= nums.length <= 105
1 <= nums[i], minK, maxK <= 106
*/

// 法一
class Solution {
	public:
	long long countSubarrays(vector<int>& nums, int minK, int maxK) {
		long long ans = 0; // 存储最终符合条件的子数组个数
		int min_i = -1, max_i = -1, i0 = -1; // 初始化 minK、maxK 和非法位置的索引
		// 遍历 nums 数组
		for (int i = 0; i < nums.size(); i++) {
			int x = nums[i]; // 当前数组元素
			if (x == minK) {
				min_i = i; // 更新最近出现 minK 的位置
			}
			if (x == maxK) {
				max_i = i; // 更新最近出现 maxK 的位置
			}
			if (x < minK || x > maxK) {
				i0 = i; // 如果元素不在 [minK, maxK] 范围内，更新非法位置
			}
			// 计算有效子数组个数：即 min_i 和 max_i 之间的有效子数组个数
			ans += max(min(min_i, max_i) - i0, 0); 
		}
		return ans; // 返回符合条件的子数组总数
	}
};
	
// 法二
class Solution {
	public:
	long long countSubarrays(vector<int>& nums, int minK, int maxK) {
		int n = nums.size(); // 数组 nums 的大小
		long long ans  = 0;  // 用于存储符合条件的子数组个数
		int min_i = -1, max_i = -1, i0 = -1; // 初始化 minK、maxK 和不符合条件的最左端位置
		// 遍历数组 nums
		for (int i = 0; i < n; i++) {
			int x = nums[i]; // 当前元素
			// 更新 minK 的最新出现位置
			if (x == minK) {
				min_i = i;
			}
			// 更新 maxK 的最新出现位置
			if (x == maxK) {
				max_i = i;
			}
			// 如果当前元素不在 [minK, maxK] 范围内，则更新不符合条件的位置 i0
			if (x < minK || x > maxK) {
				i0 = i;
			}
			// 计算当前 i 位置有效子数组的数量
			// min(min_i, max_i) 表示 minK 和 maxK 最后出现的位置
			// i0 表示第一个不符合条件的元素索引
			// 当前有效子数组的数量是 (min(min_i, max_i) - i0)，确保其非负
			ans += max(min(min_i, max_i) - i0, 0);
		}
		return ans; // 返回符合条件的子数组数量
	}
};
	